'''https://leetcode.cn/problems/count-primes/comments/
思路：
厄拉多塞筛法.
比如说求20以内质数的个数,首先0,1不是质数.
2是第一个质数,然后把20以内所有2的倍数划去.
2后面紧跟的数即为下一个质数3,然后把3所有的倍数划去.
3后面紧跟的数即为下一个质数5,再把5所有的倍数划去.以此类推.
'''

'''
优点：使用厄拉多塞筛法，就不用对每个数字都遍历一遍判断是否为素数了
原理：素数的倍数一定不是素数，所有非素数一定可以由某个素数的倍数组成
'''
class Solution:
    def countPrimes(self, n: int) -> int:
        if n < 3: # 题目要统计1到n-1之间的素数，当n = 2时，只有一个数1，所以使用n<3而不是n<2
            return 0

        # 首先生成了一个全部为1的列表
        output = [1] * n
        # 因为0和1不是质数,所以列表的前两个位置赋值为0
        output[0], output[1] = 0, 0
        '''
        1. 第一个素数为2，故从index = 2开始遍历,
        2. 终点取 int(n ** 0.5) + 1，因为求倍数时用i*i，不用这个作为终点就会超出边界
        '''
        for i in range(2, int(n ** 0.5) + 1):
            if output[i] == 1:
                # i = 2时，第一个被清0的是output[i*i]即output[4]
                output[i * i:n:i] = [0] * len(output[i * i:n:i])
        # 最后output中的数字1表明该位置上的索引数为质数,然后求和即可.
        return sum(output)

n = 100
s = Solution()
print(s.countPrimes(n))






